package com.ai.zuochengyun.phase01.class05;

public class Code02_FriendCircles {

    public static int findCircleNum(int[][] m) {
        UnionFind unionFind = new UnionFind(m.length);
        for (int i = 0; i < m.length; i++) {
            for (int j = i + 1; j < m.length; j++) {
                // i和j互相认识，那么两个集合合并
                if (m[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.sets;
    }

    private static class UnionFind {

        // 父亲节点
        private int[] parent;

        // 节点数量 size[i]=k, 如果i是代表节点，size[i]才有意义，否则无意义
        // i所在的集合大小是多少
        private int[] size;

        // 辅助结构
        private int[] help;

        // 一共有多少个集合
        private int sets;

        public UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            help = new int[n];
            sets = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        /**
         * 找到代表节点，并进行路径压缩
         * @param i
         * @return
         */
        private int find(int i) {
            int index = 0;
            // i如果不等于自己，那么就一直往上
            while (i != parent[i]) {
                // 类似Code05_UnionFind方法中的stack栈结构
                help[index++] = i;
                i = parent[i];
            }
            // 因为经过上面的while循环，index已经多加了一次，此时从help中取值时，需要先将index减一，来到存放元素的位置
            // 以i位置往上的链路变成了扁平化，后面就可以以O(1)的复杂度取头节点
            for (index--; index >= 0; index--){
                // 将沿途的节点的父亲节点都设置为i
                parent[help[index]] = i;
            }
            return i;
        }

        /**
         * 将两个集合合并
         *
         * @param i
         * @param j
         */
        public void union(int i, int j) {
            // 找到大头
            int h1 = find(i);
            // 找到小头
            int h2 = find(j);
            if (h1 != h2) {
                // 小头挂大头
                if (size[h1] >= size[h2]) {
                    size[h1] += size[h2];
                    parent[h2] = h1;
                } else {
                    size[h2] += size[h1];
                    parent[h1] = h2;
                }
                sets--;
            }
        }

        public int size() {
            return sets;
        }
    }
}
